package dynamicProgramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;



public class knapSack {
	
	public int [][]optimal;
	
	
	/**
	 * create the table for dynamic solution
	 * @param value
	 * @param weight
	 * @param max
	 * @return optimal
	 */
	
	public int [][] dynamicKnapSack(List<Integer> value, List<Integer> weight,int max ){
		
		

		optimal =new int [value.size()+1][max+1];
		
		
		for(int i=1; i< value.size()+1; i++){
			
			for(int j=1; j< max+1; j++){
				
			
				 if(j >= weight.get(i-1)){					 
					 int value_1=optimal[i-1][j];
					 int value_2=optimal[i-1][j-weight.get(i-1)]+ value.get(i-1);
					 
					 
					 optimal[i][j] = Math.max(value_1,value_2);
					 
					 
				 }
				 else{
					 optimal[i][j] = optimal[i-1][j];
				 }
				
			}
			
		}
		
		
		return optimal;
		
	}
	
	
	
	
	/**
	 * get best value and their weight from the dynamic table
	 * @param value
	 * @param weight
	 * @param max
	 * @return value_soultion
	 */
	
	public List<Integer> solution(List<Integer> value, List<Integer> weight,int max ){
		
		List<Integer> index = new ArrayList<Integer>();
		List<Integer> weight_soultion = new ArrayList<Integer>();
		List<Integer> value_soultion = new ArrayList<Integer>();
		
		//print out Max weight
		System.out.println("Maximum capacity:"+max);
		
		int optimal_value = optimal[value.size()][max];
		
		//if no best solution
		if(optimal_value == 0){
			System.out.println("No items fit into the knapsack.");
			
			
		}
		
		//return the best solution value and their weight		
		else{
			
			
		int i=value.size();
		int j=max;
		
		while(i>=1 && j >=1){
			
			while(optimal[i][j]== optimal[i-1][j]){
				i--;
			}
			
			index.add(i);
			value_soultion.add(value.get(i-1));
			weight_soultion.add(weight.get(i-1));
			
			
			j=j-weight.get(i-1);
			i--;
			
		}
		
		int total_weight =0;
	
		
		//get total weight from value weight list
		for(int k=0; k < weight_soultion.size();k++){
			
			total_weight = weight_soultion.get(k)+ total_weight;
			
		}
		
		System.out.println("Optimal knapsack: "+index);
		System.out.println("Optimal values: "+value_soultion);	
		System.out.println("Optimal weights: "+weight_soultion);		
		
		System.out.println("Optimal value taken:"+optimal_value);
		
		System.out.println("Optimal weight taken:"+ total_weight);
		
		}	
		return value_soultion;
	}
	
	/**
	 * print out matrix
	 * @param matrix
	 */
	public void printMatrix(int[][] matrix){
		try{
			int rows = matrix.length;
			int columns = matrix[0].length;
			String str ="|\t";
			
			
			for(int i=0; i< rows; i++){
				for(int j=0; j< columns; j++){
					
					str = str + matrix[i][j]+"\t";
					
				}
				System.out.println(str+"|");
				str = "|\t";
			}
			
		}catch(Exception e){System.out.println("No Matrix found. ");}
		
		
	}
	
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
